//斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： 
//
// F(0) = 0,   F(1) = 1
//F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
// 
//
// 给定 N，计算 F(N)。 
//
// 
//
// 示例 1： 
//
// 输入：2
//输出：1
//解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
// 
//
// 示例 2： 
//
// 输入：3
//输出：2
//解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
// 
//
// 示例 3： 
//
// 输入：4
//输出：3
//解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
// 
//
// 
//
// 提示： 
//
// 
// 0 ≤ N ≤ 30 
// 
// Related Topics 数组 
// 👍 153 👎 0


package leetcode.editor.cn;

import java.util.HashMap;

//Java：斐波那契数
public class P509FibonacciNumber{
    public static void main(String[] args) {
        Solution solution = new P509FibonacciNumber().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //递归
/*    public int fib(int N) {
        if ( N == 0 ) return 0;
        if ( N == 1 ) return 1;
        return fib(N-1) + fib(N-2 );
    }*/
    //迭代
    //public int fib(int N) {
    //    if ( N == 0 ) return 0;
    //    if ( N == 1 ) return 1;
    //    int a = 0;
    //    int b = 1;
    //    int c = 0;
    //    for (int i = 0; i < N-1; i++) {
    //        c = a+b;
    //        a=b;
    //        b=c;
    //    }
    //    return c;
    //}
    //备忘录+递归
    //public int fib(int n) {
    //    if (n < 1) return 0;
    //    // 备忘录全初始化为 0
    //    HashMap<Integer,Integer> map = new HashMap<>();
    //    // 进行带备忘录的递归
    //    return helper(map, n);
    //}
    //private int helper(HashMap map, int n) {
    //    // base case
    //    if (n == 1 || n == 2) return 1;
    //    // 已经计算过
    //    if (map.get(Integer.valueOf(n))!=null) return (Integer) map.get(Integer.valueOf(n));
    //    map.put(Integer.valueOf(n),helper(map,n-1)+helper(map,n-2));
    //    return (Integer) map.get(Integer.valueOf(n));
    //}

    //dp 数组的迭代解法
    public int fib(int n) {
        if ( n < 1 ) return 0;
        int res[] = new int[n+1];
        res[0] = 0;
        res[1] = 1;
        for (int i = 2 ; i < n+1; i++) {
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}